package com.tucc.hello.leetcode.no1_400.no1_200.no1_20.no1_10.no10;

/**
 * @Description:
 * @Date: 2021/5/14 15:25
 * @Author: tucc
 */
public class Solution {


    public static void main(String[] args) {
        String[] ss = {"mississippi","mis*is*ip*.","abcd", "aa", "a"};
        String[] aa = {"mississippi","mis*is*p*.","a*", "a*", "ab*"};
        // true, false, false, true
        for(int i = 0;i < ss.length;i ++) {
            String s = ss[i];
            String p = aa[i];
            System.out.println(new Solution().isMatch(s, p));
        }

        System.out.println(new Solution().isMatch("a", ".*..a*"));
    }

    final static char ANY = '.';

    final static char MORE = '*';

    final static char EMPTY_CHAR = '\u0000';

    public boolean isMatch(String s, String p) {
        return isMatch(s, p, 0, 0, false, EMPTY_CHAR);
    }

    public boolean isMatch(String s, String p, int si, int pi, boolean inMoreMatch,
                            char matchChar) {
        int pl = p.length();
        int sl = s.length();
        if (si >= sl && pi >= pl) {
            return true;
        } else if (si >= sl) {
            if(inMoreMatch){
                return isMatch(s, p, si, pi + 1, false, EMPTY_CHAR);
            }
            return (pi  < pl && p.charAt(pi) == MORE && isMatch(s, p , si, pi + 1, false, EMPTY_CHAR)) ||
                    (pi + 1 < pl && p.charAt(pi + 1) == MORE && isMatch(s, p, si, pi + 2, false, EMPTY_CHAR));
        }
        else if(pi >= pl && !inMoreMatch){
            return false;
        }
        if (!inMoreMatch) {
            boolean curMatch = p.charAt(pi) == ANY || s.charAt(si) == p.charAt(pi);
            if (pl > pi + 1) {
                // 判断 下一个是*的情况
                if (MORE == p.charAt(pi + 1)) {
                    // .*结尾的情况直接返回true
                    if (pl <= pi + 2) {
                        return p.charAt(pi) == ANY ||
                                isMatch(s, p, si, pi + 2, false, EMPTY_CHAR) ||
                                (curMatch &&
                                isMatch(s, p, si + 1, pi + 2, true, p.charAt(pi)));
                    }
                    // 1. 匹配0次当前
                    // 2. 匹配1次当前
                    // 2. 匹配多次当前
                    return isMatch(s, p, si, pi + 2, false, EMPTY_CHAR)
                            || (curMatch && (isMatch(s, p, si + 1, pi + 2, false, EMPTY_CHAR)
                            || isMatch(s, p, si + 1, pi + 1, true, p.charAt(pi))));
                } else {
                    return curMatch &&
                            isMatch(s, p, si + 1, pi + 1, false, EMPTY_CHAR);
                }
            } else {
                return curMatch && si == sl - 1;
            }
        } else {
            // 匹配多次模式下， 当前下标匹配 且 （继续匹配 或 终止多次匹配）
            return (matchChar == ANY || s.charAt(si) == matchChar) && (isMatch(s, p, si + 1, pi, true, matchChar)
                    || isMatch(s, p, si + 1, pi + 1, false, EMPTY_CHAR));
        }
    }
}
